package com.jxb.four;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 柱状图中最大的矩形
 * 输入：[2,1,5,6,2,3]
 * 输出：10
 *
 * 思路：单调栈
 *  长度计算：当前栈pop元素对应原数组的值
 *  宽度计算：当前位置索引-栈中的最顶元素-1
 */
public class LargestRectangle_84 {

    public static void main(String[] args) {

    }

    //单调栈
    public static int maxRectangle(int[] nums) {
        //记录面积
        int max = 0;
        //定义栈
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int n = nums.length;
        //遍历数组
        //i = 1
            //curIndex=0,curHeight=2,curWeight=1
        //i = 4
            //curIndex=3,curHeight=6,curWeight=1,max=6
            //curIndex=2,curHeight=5,curWeight=2,max=10
        for (int i = 1;i<n;i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                int curIndex = stack.pop();
                //获取当前元素的高
                int curHeight = nums[curIndex];
                //计算矩形的宽
                int curWeight;
                if (stack.isEmpty()) {
                    curWeight = i;
                }else {
                    curWeight = i - stack.peek() - 1;
                }
                max = Math.max(max,curHeight*curWeight);
            }
            stack.push(i);
        }
        //处理栈中剩余的元素
        //curHeight=3,curWeight=6-4-1=1,max=3
        //curHeight=2,curWeight=6-1-1=4,max=8
        //curHeight=1,curWeight=6,max=6
        while (!stack.isEmpty()) {
            int curHeight = nums[stack.pop()];
            int curWeight;
            if (stack.empty()) {
                curWeight = n;
            }else {
                curWeight = n -stack.peek() -1;
            }
            max = Math.max(max,curHeight*curWeight);
        }
        return max;
    }

    //哨兵
    public static int maxRectangleSb(int[] nums) {
        int max = 0;
        int len = nums.length;
        int[] newNums = new int[nums.length + 2];
        newNums[0] = 0;
        System.arraycopy(nums,0,newNums,1,nums.length);
        newNums[len + 1] = 0;
        len = len + 2;

        //定义栈
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for (int i = 1;i<len;i++) {
            while (newNums[i] < newNums[stack.peek()]) {
                int curIndex = stack.pop();
                //获取当前元素的高
                int curHeight = newNums[curIndex];
                //计算矩形的宽
                int curWeight;
                if (stack.isEmpty()) {
                    curWeight = i;
                } else {
                    curWeight = i - stack.peek() - 1;
                }
                max = Math.max(max, curHeight * curWeight);
            }
            stack.push(i);
        }
        return max;
    }

}
